package com.geek.spring.algorithms.sort;

import org.springframework.instrument.classloading.tomcat.TomcatLoadTimeWeaver;

import javax.xml.crypto.Data;
import java.awt.font.TextMeasurer;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import static java.util.stream.Collectors.filtering;
import static java.util.stream.Collectors.toList;

/**
 * @program java-spring
 * @description: sort
 * @author: chanzhugang
 * @create: 2021/08/19 12:36
 */
public class SortTest {

    public static void main(String[] args) {

        int[] a = new int[]{1, 9, 2, 8, 3, 7, 4, 6, 5, 5, 3};

        //   int[] insertResult = insertSort(a);
//        for (int data : insertResult) {
//            System.out.println(data);
//        }

//        int[] selectResult = selectSort(a);
//        for (int data : selectResult) {
//            System.out.println(data);
//        }

//        int[] bubbleResult = bubbleSort(a);
//        for (int data : bubbleResult) {
//            System.out.println(data);
//        }

//        int[] mergeResult = mergeSort(a);
//        for (int data : mergeResult) {
//            System.out.println(data);
//        }
//        List<Integer> list = new ArrayList<>(a.length);
//        for (int i = 0; i < a.length; i++) {
//            list.add(a[i]);
//        }
//
//        List<Integer> quickResult = quickSort(list);
//        for (Integer data : quickResult) {
//            System.out.println(data);
//        }


        List<Integer> list = new ArrayList<>(a.length);
        for (int i = 0; i < a.length; i++) {
            list.add(a[i]);
        }

        List<Integer> bucketResult = bucketSort(list);
        for (Integer data : bucketResult) {
            System.out.println(data);
        }

    }

    // 插入排序

    public static int[] insertSort(int[] a) {
        // 往有序数组里插入一个元素， 保持数组有序：  从尾部开始比较，找到元素正确的索引位置, 比他大的元素往后挪一位
        if (a.length <= 1) {
            return a;
        }
        for (int i = 0; i < a.length; i++) {
            // val 是你抓到的牌，需要插入到正确的位置
            int val = a[i];
            int j = i - 1;
            for (; j > 0; j--) {
                if (a[j] > val) {
                    // 往后挪一位
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = val;

        }
        return a;


    }

    // 选择排序：选择未排序区间最小值放在 已排序区间末尾

    public static int[] selectSort(int[] a) {
        // 找最小值放在有序区间末尾，交换位置
        // 选择无序区间里的最小值， 放在有序区间的末尾，即外层循环的索引位置，交换位置
        if (a.length <= 1) {
            return a;
        }
        for (int i = 0; i < a.length; i++) {
            // 最小值的索引
            int mixIndex = i;
            // j = i; 从无序区间找
            for (int j = i; j < a.length; j++) {
                if (a[j] < a[mixIndex]) {
                    mixIndex = j;
                }
            }
            // 交换最小值的位置
            int temp = a[i];
            // 外层循环的最小值
            a[i] = a[mixIndex];
            a[mixIndex] = temp;
        }
        return a;

    }

    // 冒泡排序
    public static int[] bubbleSort(int[] a) {
        // 比较相邻元素，交换位置
        if (a.length <= 1) {
            return a;
        }
        for (int i = 0; i < a.length; i++) {
            boolean flag = false;
            // 冒泡： 比较内层循环 相邻元素，交换位置
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
            // 没有要排序的，退出循环
            if (!flag) {
                break;
            }

        }
        return a;
    }

    // 归并排序, 取中间数，分成两个有序数组，再合并成一个有序数组
    public static int[] mergeSort(int[] a) {

        mergeSort(a, 0, a.length);

        return a;
    }

    private static void mergeSort(int[] a, int l, int r) {
        if (r - l <= 1) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(a, l, mid);
        mergeSort(a, mid, r);
        merge(a, l, mid, r);
    }

    private static void merge(int[] a, int l, int mid, int r) {
        int[] left = Arrays.copyOfRange(a, l, mid + 1);
        int[] right = Arrays.copyOfRange(a, mid, r + 1);

        left[left.length - 1] = right[right.length - 1] = Integer.MAX_VALUE;
        // 1，3，5 ｜｜ 2，4，6
        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if (left[i] < right[j]) {
                a[k] = left[i++];
            } else {
                a[k] = right[j++];
            }
        }

    }


    // 快速排序
    public static List<Integer> quickSort(List<Integer> a) {
        // 随机选择一个数， 小于这个数的放左边， 自己放中间， 大于这个数的放右边
        return quick(a);
    }

    private static List<Integer> quick(List<Integer> a) {
        // 递归中止条件
        if (a.size() <= 1) {
            return a;
        }
        // 取第一个值
        int val = a.get(0);

        List<Integer> left = a.stream().filter(data -> data < val).collect(toList());
        List<Integer> mid = a.stream().filter(data -> data == val).collect(toList());
        List<Integer> right = a.stream().filter(data -> data > val).collect(toList());
        left = quick(left);
        right = quick(right);
        left.addAll(mid);

        left.addAll(right);
        return left;

    }


    // 桶排序: 100万个数，数字全是0-99 ， 100个桶，第一个桶放0， 第二桶放1， 、、第100个桶放99
    public static List<Integer> bucketSort(List<Integer> list) {
        int k = 10;
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            // 创建100个桶
            buckets.add(new LinkedList<>());
        }

        //   将数据 取模 放入对应的桶
        for (Integer data : list) {
            buckets.get(data % k).add(data);
        }

        List<Integer> result = new ArrayList<>();
        for (LinkedList<Integer> bucket : buckets) {
            result.addAll(bucket);
        }
        return result;

    }


    // 基数排序

    // 计数排序
}